< >

Summation of Primes

TIME LIMIT = 1 SEC.

Okay, enough stories, don't you think? Let's have a straightforward problem:
Given a number N, find the sum of all primes strictly below N.

Input	Output
First line will contain N.	Print the sum of all primes strictly below N.

Constraints

1 ≤ N ≤ 10⁶

Example Test Case

Input	Output
10	17

Solution

#include <iostream> using namespace std; int main() { unsigned long long int n,i,sum=0; cin>>n; bool Sieve[n]; for(i=0;i<n;i++) Sieve[i]=true; Sieve[0]=false; Sieve[1]=false; // Check all nos from 2 to 1 million for(long i = 2; i < n; ++i) { if( Sieve[i]==false ) // If marked not prime continue; // return to head of loop else // Set all multiples as not prime for(long j = 2*i; j < n; j += i) Sieve[j] = false; } for(long i = 2; i < n; ++i) if( Sieve[i]==true ) // Add all nos with bit set sum += i; cout << sum << endl; return 0; }